/*************************************************************************
  > 作者: zhaoyong
  > 备注:  
 ************************************************************************/
#include "data.h"
//创建一个节点
//参数: [IN]: type, 类型(4为目录,8为普通文件); file_name, 文件名字面值常量; time, 修改时间
//返回值: 成功,返回初始化好的node; 失败, NULL
static node_t *make_node(int type, char *file_name, time_t time)
{
	data_t *data = (data_t *)malloc(sizeof(data_t) * 1);
	if (data == NULL) {
		return NULL;
	}
	data->type = type;
	data->file_name = (char *)malloc(strlen(file_name)+1);
	strcpy(data->file_name, file_name);
	data->time = time;
	node_t *node = (node_t *)malloc(sizeof(node_t) * 1);
	if (node == NULL) {
		free(data); 
		return NULL;
	}
	node->data = data;
	node->p = NULL;
	node->c = NULL;
	node->l = NULL;
	node->r = NULL;
	return node;
}
//插入一个节点
//参数: [IN]: 传入父节点
//返回值: 成功, 返回节点地址; 失败, 返回NULL
node_t * insert_node(node_t **f_node, int type, char *file_name, time_t time)
{
	node_t *node = make_node(type, file_name, time); //生成一个节点
	if (node == NULL) {
		perror("make_node error");	
		return NULL; //失败返回-1
	}
	if (*f_node == NULL)	{ //为空的树
		*f_node = node;
		return node;
	} else { //树非空
		node_t *tmp_node = (*f_node)->c; //保存父节点的 c 指针域
		if (tmp_node == NULL) { //该父节点无子节点, 该节点为父的直接子节点, 也是同层中的最左节点
			(*f_node)->c = node;	
			node->p = *f_node;
			return node;
		} else { //该父节点有子节点
			for (; tmp_node->r; tmp_node = tmp_node->r)	 //找父节点下一层的最右节点
				; //退出循环, tmp_node为最右节点
			tmp_node->r = node;
			node->l = tmp_node;
			return node;
		}
	}
}
void print_node(node_t *node, int n)
{
	while (n-- > 0) {
		printf("\t");
	}
	char tmp[1024];
	char *str = ctime(&node->data->time);
	strcpy(tmp, str);
	tmp[strlen(str)-1] = '\0';
	printf("type:[%u], time:[%s], name[%s], addr[%p]\n", node->data->type, tmp, node->data->file_name, node);
}
//打印树
//打印本节点及其子节点, 右节点
void print_tree(node_t *root, int n)
{
	if (root == NULL) {
		return ;
	}
	print_node(root, n); //打印本节点
	print_tree(root->c, n+1); //打印本节点的子节点
	node_t *tmp;
	print_tree(root->r, n); //打印本节点的右节点
	return ;
}
//将一个节点的空间释放
static void free_a_node(node_t *node)
{
	if (node == NULL) {
		return ;
	}
	free(node->data->file_name);
	free(node->data);
	free(node);
}
//将整个树删除
node_t *delete_tree(node_t *root)
{
	if (root == NULL) {
		return ;
	}
	delete_tree(root->c); //删除子节点
	delete_tree(root->r); //删除右节点

	if (root->l != NULL) { //非最左节点
		root->l->r = NULL;
	} else { //也是最左节点
		if (root->p != NULL) { //非根节点
			root->p->c = NULL;	
		} else { //根节点
			free_a_node(root);
			return NULL;
		}
	}
	free_a_node(root);
	return NULL;
}

//将本节点及其子节点删除
node_t *delete_node(node_t *node)
{
	if (node == NULL) {
		return ;
	}
	delete_tree(node->c); //删除子节点
	
	if (node ->r != NULL) { //非最右节点
		node ->l->r = node ->r;
		node ->r->l = node ->l;
	} else { //是最右节点
		if (node ->l != NULL) { //非最左节点
			node ->l->r = NULL;
		} else { //也是最左节点
			if (node->p != NULL) { //非根节点
				node->p->c = NULL;	
			} else { //根节点
				free_a_node(node);
				return NULL;
			}
		}
	}
	free_a_node(node);
	return NULL;
}

